class Heap<T> {
  data: T[] = [];
  private length: number = 0;

  //根据索引交换数组里的数据
  private swap(i: number, j: number) {
    const temp = this.data[i];
    this.data[i] = this.data[j];
    this.data[j] = temp;
  }

  //方法
  insert(value: T) {
    //新加入的插入数组最后面
    this.data.push(value);
    this.length++;
    this.percolateUp();
  }

  //上滤操作
  protected percolateUp() {
    let index = this.length - 1;
    let parentIndex = Math.floor((index - 1) / 2);

    while (index > 0) {
      if (this.data[index] <= this.data[parentIndex]) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  //提取  删除
  extract(): T | undefined {
    //边界判断
    if (this.length === 0) return undefined;
    if (this.length === 1) {
      this.length--;
      return this.data.shift();
    }

    //其他情况需要将最后一个元素提取top，然后进行下滤操作

    const topValue = this.data[0];
    this.data[0] = this.data.pop()!;
    this.length--;
    this.percolateDown();
    return topValue;
  }

  //下滤操作
  private percolateDown() {
    let index = 0;

    while (2 * index + 1 <= this.length - 1) {
      let leftChildrenIndex = 2 * index + 1;
      let rightChildrenIndex = 2 * index + 2;

      let largerIndex = leftChildrenIndex;

      if (
        rightChildrenIndex < this.length &&
        this.data[rightChildrenIndex] > this.data[leftChildrenIndex]
      ) {
        largerIndex = rightChildrenIndex;
      }

      if (this.data[index] > this.data[largerIndex]) {
        break;
      }

      this.swap(index, largerIndex);
      index = largerIndex;
    }
  }

  peek(): T | undefined {
    return this.data[0];
  }

  size(): number {
    return this.data.length;
  }

  isEmpty() {
    return this.length === 0;
  }

  buildHeap(arr: T[]) {}
}

const heap = new Heap<number>();

const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7];

arr.forEach(v => {
  heap.insert(v);
});

console.log(heap.extract());
console.log(heap.extract());
console.log(heap.extract());

console.log(heap.data);

export {};
